package leetCode.hw.dp;


public class HJ16Solution implements HJ16 {

    /**
     * 购物车问题求解
     * 由于存在附件问题，则进行选择时比普通的背包问题多了一些情况：
     * 1. 不选择该物品
     * 2. 选择该物品
     * 3. 选择该物品和其附件1
     * 4. 选择该物品和其附件2
     * 5. 选择该物品和其附件1+2
     * @param money
     * @param items
     * @return
     */
    public int getMaxPrice(int money, Item[] items) {

        int m = items.length;
        int[][] dp = new int[m+1][money+1];
        //dp[0][x] dp[x][0] 都默认为0

        for(int i=1;i<=m;i++) {
            for(int j=1;j<=money;j++) {
                dp[i][j] = dp[i-1][j];
                // 只处理主件
                if(items[i-1].parentId==-1) {
                    // 当前物品是主件，放入背包
                    if(j-items[i-1].price>=0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - items[i-1].price] + items[i-1].goodNum);
                    }

                    // 主件+附件1
                    if(items[i-1].sub1!=null&&j - items[i-1].price - items[i-1].sub1.price>=0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - items[i-1].price - items[i-1].sub1.price] + items[i-1].goodNum+items[i-1].sub1.goodNum);
                    }

                    // 主件+附件2
                    if(items[i-1].sub2!=null&&j - items[i-1].price - items[i-1].sub2.price>=0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - items[i-1].price - items[i-1].sub2.price] + items[i-1].goodNum+items[i-1].sub2.goodNum);
                    }

                    // 主件+附件1+附件2
                    if(items[i-1].sub1!=null&&items[i-1].sub2!=null&&(j - items[i-1].price-items[i-1].sub1.price-items[i-1].sub2.price)>=0){
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - items[i-1].price - items[i-1].sub1.price-items[i-1].sub2.price]
                                + items[i-1].goodNum+items[i-1].sub1.goodNum+items[i-1].sub2.goodNum);
                    }
                }

            }
        }
        return dp[m][money];
    }

    public static void main(String[] args) {
        Item[] items = new Item[5];
        items[0] = new Item(800,2,-1);
        items[1] = new Item(400,5,0);
        items[2] = new Item(300,5,0);
        items[3] = new Item(400,3,-1);
        items[4] = new Item(500,2,-1);
        items[0].sub1 = items[1];
        items[0].sub2 = items[2];
        System.out.println(new HJ16Solution().getMaxPrice(1000,items));
    }

}

class Item {
    public int price;
    public int goodNum;
    public int parentId;
    public Item sub1;
    public Item sub2;

    public Item(int price,int important,int parentId) {
        this.price = price;
        this.goodNum = important*price;
        this.parentId = parentId;
    }

}
